문제https://www.acmicpc.net/problem/2688문제어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T(1 출력각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한..
전체 글
항공대 알고리즘 동아리 Koala 🥰문제문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.출력단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.예제 입력 1 복사baekjoon예제 출력 1 복사1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 https://www.acmicpc.net/problem/10808 Algorithm1.사용자로 부터 소문자로만 이루어진 단어 s를 입력받는다.2.알파벳 소문자의 아스키코드를 이용하여 아스키코드를 하나씩 늘려가며 모든 알파벳의 개수를 파악할..
문제 https://www.acmicpc.net/problem/10867문제N개의 정수가 주어진다. 이때, N개의 정수를 오름차순으로 정렬하는 프로그램을 작성하시오. 같은 정수는 한 번만 출력한다. 입력 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 수를 오름차순으로 정렬한 결과를 출력한다. 이때, 같은 수는 한 번만 출력한다. Algorithm1. 정수를 리스트로 입력받는다2. 수의 중복을 막기 위해 리스트를 set으로 바꿨다 다시 리스트로 바꿔준다3. 리스트에 sort를 써서 정렬시킨뒤 출력한다 Codeimport sysN = int(sys.stdin.readline())..
https://www.acmicpc.net/problem/15724 전형적인 누적합 문제라 이게 왜 DP에 있지? 하는 고민이 들었습니다찾아보니 이런 식의 누적합 풀이법도 사실 DP 테이블을 사용하고 채우므로, 넓은 의미에서 DP 풀이가 맞다고 하더라구요! import sysinput = sys.stdin.readline def main(): n,m = map(int,input().split()) ground = [] for _ in range(n): ground.append(list(map(int,input().split()))) prefixSum = [[0 for i in range(m+1)] for j in range(n+1)] for i in ran..
문제 & 링크https://www.acmicpc.net/problem/2133 풀이1. bottom-up 방식으로 dp 테이블을 채운다.2. 타일의 크기가 2이기 때문에 N이 홀수일 경우 벽을 채울 수 없다. 따라서 N이 짝수일 경우만 생각한다.3. 기본적으로 N이 2씩 증가될 때 마다 기존의 개수에 3을 곱해준다. (3 x 2의 타일을 채우는 방법이 3가지)4. N이 2씩 증가되며 새로운 모양이 등장한다.5. 위의 모양을 고려하여 점화식을 구한다. (아래의 사진 참고)코드#include using namespace std;int dp[31];int main() { int N; cin >> N; dp[0] = 1; // dp 테이블을 채우기 위함 dp[2] = 3; int su..
문제 https://www.acmicpc.net/problem/16571Algorithm min-max 알고리즘의 기본 형태A와 B가 순서대로 뽑고, 기본 행동 원리는 상대의 이익을 최소화 하기 위해 행동하는 것이다.예를 들어 숫자 3개가 들어있는 박스가 3개가 있다. [3,5,7] [1,2,4] [5,6,8] 상대 플레이어는 여기서 숫자를 하나씩 뽑아서 새로운 숫자 박스를 만든다. [x1,x2,x3] 그리고 상대는 여기서 뽑은 숫자가 상대의 점수가 된다고 했을 때 그 점수를 최소화 하기 위해서는 가장 작은 숫자들만 남기는 것이다. (min) 그렇게 되면 [3,1,5]가 될 것이고, 이 박스에서 가장 큰 숫자를 고를 것이다.(max)이것이 간단한 min-max인데 틱택토에서 현재 board의 상태에서 계..
문제문제졸업을 앞둔 연길이는 크리스마스가 다가올수록 외로움을 느낀다.그런 연길이를 위해 동우는 소개팅을 시켜주지는 않고 연길이의 이상향을 찾는 것을 도와주고자 한다.MBTI 신봉자인 연길이는 자신과 정반대인 사람에게 매력을 느낀다. 즉, MBTI의 네가지 지표가 모두 자신과 반대인 사람이 연길이의 이상형이다.MBTI는 다음과 같은 네 가지 척도로 성격을 표시한다. 각각의 척도는 두 가지 극이 되는 성격으로 이루어져 있다.지표설명외향(Extroversion)내향(Introversion)선호하는 세계:세상과 타인 / 내면 세계감각(Sensation)직관(iNtuition)인식형태: 실제적인 인식/ 실제 너머로 인식사고(Thinking)감정(Feeling)판단기준: 사실과 진실 위주 / 관계와 사람 위주판단(..
문제 https://www.acmicpc.net/problem/2839문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)출력..
문제 https://www.acmicpc.net/problem/15686 문제크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |..
문제 & 링크https://www.acmicpc.net/problem/20529 풀이1. 입력 및 출력의 개수가 많기에 빠른 입출력을 사용한다.2. MBTI의 개수는 16개이기에 비둘기집 정리에 의해 N이 33개 이상이면 무조건 같은 MBTI 3개가 나온다. 따라서 N이 33개 이상일 때는 답을 0으로 출력해준다.3. N의 개수를 100,000개에서 최대 32개로 줄였으니, 백트래킹을 사용하여 MBTI 조합을 찾아준다. 이때 depth를 사용하여 현재 조합 내에 있는 MBTI의 개수를 판단해준다.4. depth가 3일 경우 심리적 거리를 계산해준다.5. 계산식은 E_cnt * I_cnt + S_cnt * N_cnt + T_cnt * F_cnt + J_cnt * P_cnt이다.6. 심리적 거리의 최솟..
문제 https://www.acmicpc.net/problem/2164 Algorithm Code#include #include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); queue Q; int N; cin >> N; for (int i=1;i
https://www.acmicpc.net/problem/2740 단순 행렬곱셈 문제이다. 우리에겐 넘파이가 있지만... 백준에선 직접 곱해주어야 한다.def main(): n, _ = map(int,input().split()) arr = [] for _ in range(n): arr.append(list(map(int,input().split()))) m, k = map(int,input().split()) brr = [] for _ in range(m): brr.append(list(map(int,input().split()))) ans = [[[0] for _ in range(k)] for i in range(n)] ..